// 给你一个链表数组，每个链表都已经按升序排列。

// 请你将所有链表合并到一个升序链表中，返回合并后的链表。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;


  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 

// 执行用时：
// 668 ms
// , 在所有 C++ 提交中击败了
// 5.39%
// 的用户
// 内存消耗：
// 13.9 MB
// , 在所有 C++ 提交中击败了
// 17.68%
// 的用户
// 直接遍历

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len =lists.size();
        ListNode* res = new ListNode();
        if(len==0){
            return NULL;
        }
        vector<ListNode*> res_list;
        while(true){
            int imin = INT_MAX;
            int pos_min=-1;
            for(int i=0;i<len;i++){
                if(lists[i]!=NULL){
                    if(imin>lists[i]->val){
                        imin=lists[i]->val;
                        pos_min=i;
                    }
                }
            }
            if(pos_min==-1){
                break;
            }
            ListNode* temp = new ListNode(imin);
            res_list.push_back(temp);
            lists[pos_min]=lists[pos_min]->next;
        }
        ListNode* cur = res;
        for(int i=0;i<res_list.size();i++){
            cur->next=res_list[i];
            cur=cur->next;
        }
        return res->next;
    }
};